We consider the following problem: given a robot system, find a minimal-time trajectory from a start position and velocity to a goal position and velocity, while avoiding obstacles and respecting dynamic constraints on velocity and acceleration. Based on the theoretical results of [CDRX], we have developed and implemented a new, provably good approximation algorithm for the minimum-time trajectory problem. Our algorithm differs from previous work in three ways. First, it is possible to bound the goodness of the approximation by an error term $\epsilon$. Second, we can polynomially bound the running time (complexity) of our algorithm. Third, we can express the complexity as a polynomial function of the error term. Hence, one supplies the algorithm with the geometric obstacles, dynamics bounds, and the error term $\epsilon$. The algorithm returns a solution that is $\epsilon$-close to optimal, and promises to spend only a polynomial (in $(\frac{1}{\epsilon})$) amount to time computing the answer. In this paper, we describe the algorithm and explain the results in simple terms. We show how it can be applied to robotics, and report on an implementation and experiments.
展开▼
